//
//  DouglasPeucker.swift
//  MeasureMould
//
//  Created by iOS on 2021/5/28.
//

import Foundation

class DouglasPeucker{
    func compressLine(pointList:[CLLocationCoordinate2D], epsilon:Double) -> [CLLocationCoordinate2D]{
        // 找到最大阈值点
        var maxH:Double = 0
        var index = 0
        let end = pointList.count
        for i in 1 ..< end {
            let h = pointToLineHeight(pointA: pointList[0], pointB: pointList[i], pointC: pointList[end-1])
            if h > maxH {
                maxH = h
                index = i
            }
        }
        //如果存在最大阈值，就进行递归遍历出所胡最大阈值点
        var result:[CLLocationCoordinate2D] = []
        if maxH > epsilon {
            var leftPoints:[CLLocationCoordinate2D] = [] // 左曲线
            var rightPoints:[CLLocationCoordinate2D] = [] //右曲线
            //分别提取出左曲线和右曲线的坐标点
            for i in 0 ..< end {
                if i < index {
                    leftPoints.append(pointList[i])
                    if i == index {
                        rightPoints.append(pointList[i])
                    }
                }else{
                    rightPoints.append(pointList[i])
                }
            }
            // 分别保存两边遍历的结果
            var leftResult:[CLLocationCoordinate2D] = []
            var rightResult:[CLLocationCoordinate2D] = []
            leftResult = compressLine(pointList: leftPoints, epsilon: epsilon)
            rightResult = compressLine(pointList: rightPoints, epsilon: epsilon)

            // 将两边的结果整合
            if rightResult.count > 0 {
                rightResult.remove(at: 0)
            }
            leftResult.append(contentsOf: rightResult)
            result = leftResult
        }
        else{
            // 如果不存在最大阈值点刚返回当前遍历的了曲线的起始点
            result.append(pointList[0])
            result.append(pointList[end-1])
        }
        return result
    }

    /// 计算点到直线的距离
    func pointToLineHeight(pointA:CLLocationCoordinate2D, pointB:CLLocationCoordinate2D, pointC:CLLocationCoordinate2D) -> Double{
        let a = fabs(distance(startPoint: pointA, endPoint: pointB))
        let b = fabs(distance(startPoint: pointA, endPoint: pointC))
        let c = fabs(distance(startPoint: pointB, endPoint: pointC))
        let S = hailunToArea(a, b: b, c: c)
        let height = 2 * S / a
        return height
    }


    /// 计算两点间的距离
    func distance(startPoint:CLLocationCoordinate2D, endPoint:CLLocationCoordinate2D) -> Double {
//        let point1 = MAMapPointForCoordinate(startPoint)
//        let point2 = MAMapPointForCoordinate(endPoint)
//        return MAMetersBetweenMapPoints(point1, point2)
        let point1 = CLLocation(latitude: startPoint.latitude, longitude: startPoint.longitude)
        let point2 = CLLocation(latitude: endPoint.latitude, longitude: endPoint.longitude)
        let distance = point1.distance(from: point2)
        return distance
    }

    /// 海伦公式计算三角形面积
    /// S = √p(p-a)(p-b)(p-c)
    /// - Parameters:
    ///   - a: a边
    ///   - b: b边
    ///   - c: c边
    /// - Returns: 面积
    func hailunToArea(_ a:Double, b:Double, c:Double) -> Double {
        var s:Double = 0
        let pp:Double = (a + b + c) / 2.0
        s = sqrt(fabs(pp * (pp - a) * (pp - b) * (pp - c)))
        return s
    }
}
